import java.util.Arrays;

/**
 * @author ChenJunhong
 * @date 2018/11/02
 * Description:
 * 堆排序的步骤：
 * 1. 初始化最大堆
 * 2. 交换最大堆的根节点与尾节点
 * 3. 对剩余节点进行重复的操作，直到只剩下1个节点
 * 本代码基于下标从0开始计算，此时：
 * 节点i的左节点为 2*i + 1， 右节点为2*i + 2
 */
public class HeapSort {


    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){

        // 初始化最大堆
        // 当 i = n/2 时，n为奇数时，左节点为n，偶数时，左节点为n
        // 当 i> n/2时，左右节点的下标均 > n
        // 因此 n/2 是最后一个有子节点的节点了
        for (int i = arr.length / 2 ; i >= 0; i--){
            maxHeapify(arr,i,arr.length);
            //minHeapify(arr,i,arr.length);
        }

        for (int i = arr.length - 1; i > 0 ; i--) {
            // 交换根节点--最大或者最小节点，与最后一个节点的值
            swap(arr,0,i);
            // 对剩余的数据再次进行最大堆调整
            maxHeapify(arr,0,i);
            //minHeapify(arr,0,i);
            System.out.println(Arrays.toString(arr));
        }
    }


    /**
     * 最大堆化
     * @param arr 需要最大堆化的数组
     * @param parent
     * @param length
     */
    private static void maxHeapify(int[] arr,int parent,int length){

        int temp = arr[parent];
        // 从左节点开始
        int child = 2 * parent + 1;

        while (child < length){
            // 如果有孩子节点存在，且有孩子节点的值比左孩子节点的值要大，那么替换为右孩子节点
            if (child + 1 < length && arr[child] < arr[child + 1]){
                child ++;
            }

            // 如果父节点的值最大，那么就已经不需要调整了
            if (temp >= arr[child]){
                break;
            }

            // 将孩子节点的值赋予父节点
            arr[parent] = arr[child];

            // 从孩子节点的左孩子节点继续循环
            parent = child;
            child = 2*child + 1;
        }

        // 有两个作用
        // 1: 如果没有parent没有子节点，那么就把parent节点的值设置回来
        // 2: 如果parent有子节点，且符合交换的条件，那么现在这个parent就是之前的子节点，因为之前的子节点的值已经被替换到了父节点上，因此此操作是为了将父节点的值赋给之前的子节点
        arr[parent] = temp;

    }

    /**
     * 最小堆化
     */
    private static void minHeapify(int[] arr,int parent,int length){

        int temp = arr[parent];
        // 从左节点开始
        int child = 2 * parent + 1;

        while (child < length){
            // 如果有孩子节点存在，且有孩子节点的值比左孩子节点的值要大，那么替换为右孩子节点
            if (child + 1 < length && arr[child] > arr[child + 1]){
                child ++;
            }

            // 如果父节点的值最大，那么就已经不需要调整了
            if (temp <= arr[child]){
                break;
            }

            // 将孩子节点的值赋予父节点
            arr[parent] = arr[child];

            // 从孩子节点的左孩子节点继续循环
            parent = child;
            child = 2*child + 1;
        }

        arr[parent] = temp;
    }

    /**
     * 交换数组中的数据的位子
     * @param arr
     * @param x
     * @param y
     */
    public static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {34,5,6,3,78};
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
    }



}
